#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<iterator>
using namespace std;

const int INF = 0x7fffffff;     // a maxinum number

template<class T> class Vertex;             // the point class

template<class T>
class InfoTable {       // some information of a point
public:
    bool Known;         // just declare if this point has been through
    int dist;           // the distance
    T Path;             //  the name
};

template<class T>
class Vertex {          // point
public:
    T value;       
    vector<Vertex<T>> adj_list;     // adjacency list
    InfoTable<T>* table;       
    Vertex(T value = 0) :value(value) {}
};

template<class T>
class Graph{             
public:
    vector<Vertex<T>> VSet;    
    Graph(int sz) :size(sz) {} 
    Graph(const Graph<T> &G) { size = G.size;VSet = G.VSet; } 
  void UnweightPath(int index);    //the function   
  void InitInfoTable();            // Initialization information
  void PrintPath(int index);       //show the path

    void UnweightPathQ(int index);      // the function of using of Queue

private:
    int size;                        //the number of points              
};

template<class T>
void Graph<T>::InitInfoTable()  
{
    for (int i = 0;i < size;i++)
    {
        VSet[i].table = new InfoTable<T>[size]; 
        for (int j = 0;j < size;j++)
        {
            VSet[i].table[j].Known = false;     
            VSet[i].table[j].dist = INF;        
            VSet[i].table[j].Path = -1;         
        }
        VSet[i].table[i].dist = 0;              
    }
}

template<class T>
void Graph<T>::UnweightPath(int index)      
{
    if (index >= size)
        cout << "Out of range";
    int Currdist;       

    for (Currdist = 0;Currdist < size;Currdist++)
    {
        for (int i = 0;i < size;i++)     
        {
            if (VSet[index].table[i].Known == false && VSet[index].table[i].dist == Currdist)   
            {
                VSet[index].table[i].Known = true;  
                for (vector<Vertex<T>>::iterator iter = VSet[i].adj_list.begin();iter != VSet[i].adj_list.end();iter++)     
                {
                    if (VSet[index].table[iter->value].dist == INF)     
                    {
                        VSet[index].table[iter->value].dist = Currdist + 1;   
                        VSet[index].table[iter->value].Path = VSet[i].value;
                    }
                }
            }
        }
    }
}

template<class T>
void Graph<T>::UnweightPathQ(int index)
{
    queue<Vertex<T>> Q;     
    Vertex<T> W;
    Q.push(VSet[index]);    

    while (!Q.empty())      
    {
        W = Q.front();      
        Q.pop();            
        VSet[index].table[W.value].Known = true;        

        for (vector<Vertex<T>>::iterator iter = W.adj_list.begin(); iter != W.adj_list.end();iter++)        
        {
            if (VSet[index].table[iter->value].dist == INF)   
            {
                VSet[index].table[iter->value].dist = VSet[index].table[W.value].dist + 1;  
                VSet[index].table[iter->value].Path = VSet[W.value].value;      
                Q.push(VSet[iter->value]);    
            }
        }
    }
}

template<class T>
void Graph<T>::PrintPath(int index)
{
    cout << "The InfoTable of V" << index << " is:\n";
    for (int i = 0;i < size;i++)   
    {
        cout<<"V"<<i<<"  "<<VSet[index].table[i].Known<<"  " << VSet[index].table[i].dist
            << "  "<<"V"<< VSet[index].table[i].Path << endl;
    }
    cout << "\nShow the unweighted paths form V"<< index << " to other vertices: \n";
    stack<T> S;         
    for (int i = 0;i < size;i++)
    {
        int j = i;      
        S.push(VSet[j].value);
        while (VSet[index].table[j].Path != -1)
        {
            S.push(VSet[index].table[j].Path); 
            j = VSet[index].table[j].Path;    
        }
        while (!S.empty())                    
        {
            cout << "->";
            cout << "V" << S.top();
            S.pop();
        }
        cout << endl;
    }
    cout << endl;
}
